package main.leetcode.offer.firstround.from51to68;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 57-II.和为s的连续正数序列
 *
 * <p>输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * <p>序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 * <p>
 *
 * <p>示例 1：输入：target = 9 输出：[[2,3,4],[4,5]]
 *
 * <p>示例 2：输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *
 * <p>限制：1 <= target <= 10^5
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex57II {
    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new ex57II().findContinuousSequence(9)));
    }

    public int[][] findContinuousSequence(int target) {
        if (target < 3) return new int[][] {{1}};
        int i = 1, j = 1, curSum = 0;
        List<int[]> res = new ArrayList<>();
        int[] tmp;
        while (i <= target / 2) {
            if (curSum < target) curSum += j++;
            else if (curSum > target) curSum -= i++;
            else {
                tmp = new int[j - i];
                for (int k = 0; k < j - i; ++k) tmp[k] = k + i;
                res.add(tmp);
                curSum -= i++;
            }
        }
        return res.toArray(new int[][] {});
    }
}
